package com.lw.leetcode.sort.c;

import com.lw.test.util.Utils;

import java.util.*;

/**
 * Created with IntelliJ IDEA.
 * sort
 * 2402. 会议室 III
 *
 * @author liw
 * @version 1.0
 * @date 2022/9/5 13:12
 */
public class MostBooked {

    public static void main(String[] args) {
        MostBooked test = new MostBooked();

        // 0
//        int[][] arr = {{18,19},{3,12},{17,19},{2,13},{7,10}};
//        int k = 4;

//        int[][] arr = {{0,10},{1,5},{2,7},{3,4}};
//        int k = 2;

        // 1
//        int[][] arr ={{1,20},{2,10},{3,5},{4,9},{6,8}};
//        int k = 3;

        // 1
        int[][] arr = Utils.getArr2("C:\\lw\\aaa.txt");
        int k = 100;

        int i = test.mostBooked(k, arr);
        System.out.println(i);

    }

    public int mostBooked(int n, int[][] meetings) {
        PriorityQueue<Long> queue = new PriorityQueue<>();
        TreeSet<Integer> set = new TreeSet<>();

        Arrays.sort(meetings, (a, b) -> Integer.compare(a[0], b[0]));
        for (int i = 0; i < n; i++) {
            set.add(i);
        }
        int[] arr = new int[n];
        for (int[] meeting : meetings) {
            int a = meeting[0];
            long b = meeting[1];
            while (!queue.isEmpty()) {
                long t = queue.peek();
                long v = t >> 8;
                int c = (int) (t & 0XFF);
                if (v > a) {
                    break;
                }
                queue.poll();
                set.add(c);
            }
            if (!set.isEmpty()) {
                int f = set.first();
                set.remove(f);
                queue.add((b << 8) + f);
                arr[f]++;
                continue;
            }
            long t = queue.poll();
            long v = t >> 8;
            int c = (int) (t & 0XFF);
            queue.add(((v - a + b) << 8) + c);
            arr[c]++;
        }
        int maxIndex = n - 1;
        int max = arr[maxIndex];
        for (int i = n - 1; i >= 0; i--) {
            if (arr[i] >= max) {
                max = arr[i];
                maxIndex = i;
            }
        }
        return maxIndex;
    }

}
